package com.study.algorithm.linkedList;

import java.util.HashMap;
import java.util.Map;

public class LRUCache {

    //146. LRU 缓存
    private Map<Integer, DLinkedNode> cache = new HashMap<>(); // 哈希表存储 key -> 节点
    private int size;     // 当前缓存大小
    private int capacity; // 缓存容量
    private DLinkedNode head, tail; // 虚拟头尾节点（哨兵节点）

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        head = new DLinkedNode(); // 虚拟头节点
        tail = new DLinkedNode(); // 虚拟尾节点
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            return -1; // key 不存在
        }
        moveToHead(node); // 将节点移到头部（表示最近使用）
        return node.value;
    }

    public void put(int key, int value) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            // 如果 key 不存在，创建新节点
            DLinkedNode newNode = new DLinkedNode(key, value);
            cache.put(key, newNode); // 加入哈希表
            addToHead(newNode);      // 添加到链表头部
            size++;
            if (size > capacity) {
                // 如果超容，删除尾部节点（最久未使用）
                DLinkedNode tail = removeTail();
                cache.remove(tail.key); // 同步删除哈希表中的项
                size--;
            }
        } else {
            // 如果 key 存在，更新 value 并移到头部
            node.value = value;
            moveToHead(node);
        }
    }

    // 将节点添加到链表头部
    private void addToHead(DLinkedNode node) {
        // 步骤①：让 node 的 prev 指向 head
        node.prev = head;       // head ← node
        // 步骤②：让 node 的 next 指向原第一个节点（head.next）
        node.next = head.next;  // node → head.next
        // 步骤③：让原第一个节点的 prev 指向 node
        head.next.prev = node;  // node ← head.next
        // 步骤④：让 head 的 next 指向 node
        head.next = node;       // head → node
    }

    // 从链表中移除节点
    private void removeNode(DLinkedNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    // 将节点移动到头部（先删除再插入）
    private void moveToHead(DLinkedNode node) {
        removeNode(node);
        addToHead(node);
    }

    // 移除尾部节点（最久未使用）
    private DLinkedNode removeTail() {

        DLinkedNode res = tail.prev;
        removeNode(res);
        return res;
    }
}